package _3_TwoPointers;

import _2_Linkedlist.ListNode;

public class A22_getKthFromEnd {
    //两次遍历链表,一个指针
    public ListNode getKthFromEnd(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            count ++;
        }
        if (k - count < 0)
            throw new RuntimeException("输入k有问题");

        cur = head;
        for (int i = 0; i < (count - k); i++) {
            cur = cur.next;
        }
        return cur;
    }
    //快慢指针,两个指针，一前一后;
    public ListNode getKthFromEnd2(ListNode head, int k) {
        if(head == null || k == 0) //考虑特殊情况1、3
            return null;

        ListNode cur = head,pre = head;
        for (int i = 0; i < k; i++) {
            //检查情况2
            if(cur == null && i<k)
                return null;
            cur = cur.next;
        }
        while (cur !=null){
            pre = pre.next;
            cur = cur.next;
        }
        return pre;
    }
}


